package junior.回溯法.四阶幻方;

public class 暴力回溯求解法 {
    static int N = 4;  // 4阶幻方：基本形式880个，翻转旋转将会有7040(程序跑半小时)
    static int[] stack = new int[100];
    static int[] visit = new int[100];  // 0:未标记，1：标记
    static int top = 0;
    static int total1 = 0,total2 = 0; // 解空间个数，解的个数
    public static void main(String[] args) {
        long t1 = System.currentTimeMillis();
        fun1(0);
        long t2 = System.currentTimeMillis();
        System.out.println("求解的时间："+(t2-t1)+"  ms\t"+(t2-t1)/1000+"  s");
        System.out.println("解空间个数："+total1);
        System.out.println("正解的个数："+total2);
    }

    /**
     * n=3个元素里面取 n=3 个，进行组合，不允许重复（C（3,3，） = 1 结果只有一个）
     * @param n
     */
    public static void fun1(int n){
        if(n == N*N){
            if(check(stack,N) == true){
                for (int i = 0; i < top; i++) {
                    System.out.print(stack[i]+"\t");
                }
                System.out.println();
                total2++;
            }
            total1++;
            return;
        }
        for (int i = 1; i <= N*N; i++) {
            if(visit[i] == 1){
                continue;
            }
            if(top == 7+1 ){
                if(stack[0]+stack[1]+stack[2]+stack[3] != stack[4]+stack[5]+stack[6]+stack[7])
                    continue;
            }
            if(top == 11+1 ){
                if(stack[8]+stack[9]+stack[10]+stack[11] != stack[4]+stack[5]+stack[6]+stack[7])
                    continue;
            }
            if(top == 12+1 ){
                if(stack[0]+stack[4]+stack[8]+stack[12] != stack[4]+stack[5]+stack[6]+stack[7])
                    continue;
            }
            if(top == 12+1 ){
                if(stack[0]+stack[4]+stack[8]+stack[12] != stack[3]+stack[6]+stack[9]+stack[12])
                    continue;
            }
            // if(top >=13 ){
            //     if(stack[1]+stack[5]+stack[9]+stack[13] != stack[3]+stack[6]+stack[9]+stack[12])
            //         continue;
            // }
            visit[i] = 1;  // 已经使用
            stack[top++] = i;
            fun1(n+1);
            visit[i] = 0;  // 未使用（初试值为0）
            top--;
        }
    }

    public static boolean check(int[] check,int N) { // N:阶数

        boolean isOk = true;
        int[] row = new int[N*2+2];
        row[0] = stack[0]+stack[1]+stack[2]+stack[3];
        row[1] = stack[4]+stack[5]+stack[6]+stack[7];
        row[2] = stack[8]+stack[9]+stack[10]+stack[11];
        row[3] = stack[12]+stack[13]+stack[14]+stack[15];

        row[4] = stack[0]+stack[4]+stack[8]+stack[12];
        row[5] = stack[1]+stack[5]+stack[9]+stack[13];
        row[6] = stack[2]+stack[6]+stack[10]+stack[14];
        row[7] = stack[3]+stack[7]+stack[11]+stack[15];

        row[8] = stack[0]+stack[5]+stack[10]+stack[15];
        row[9] = stack[3]+stack[6]+stack[9]+stack[12];
        for (int i = 1; i < N*2+2; i++) {
            if (row[i] == row[i-1])
                isOk = true;
            else {
                isOk = false;
                break;
            }
        }
        return isOk;
    }
}
